package com.itheima.binarysearch;

public class BinarySearchRightMost {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 4, 5, 5, 5, 7};
        //System.out.println(binarySearchRightMost(arr, 4));
        System.out.println(binarySearchRightMostAlter(arr, 6));
    }

    public static int binarySearchRightMost(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1; //找到了更新,没找到返回-1
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                candidate = m;//记录候选位置
                i = m + 1;//继续向左找
            }
        }
        return candidate;
    }

    public static int binarySearchRightMostAlter(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;//继续向左找
            }
        }
        return i - 1;   //返回 <= target的最右索引
    }
}
